#!usr/bin/env python  
# -*- coding:utf-8 -*-
""" 
@author:robot
@file: func.py 
@version:
@time: 2024/01/22 

整数num划分，划分的树需要在0和max_num之间

num=4
max_num=4

4+0、1+3、2+2、1+1+1+1、2+1+1

若想通过分治来解决问题，需要寻找子问题，那么子问题就是这种划分方案中是否包含max_num这个数字。

据此分为两种情况：

一是此划分方案中不包含max_num,那么相当于问题变为max_num=max_num-1，num保持不变；

二是此划分方案中包含max_num，那么问题转换为max_num不变，num变为num-max_num。


当max_num与num二者中出现小于1的情况时，返回0，此时没有划分方案与之对应；
当max_num与num二者中出现等于1的情况时，返回1，此时只有一种划分方案；
当max_num大于num时，此时是异常情况，因为最大加数必定小于num本身，问题会转换为max_num=num；
当max_num小于num时，相当于又一种划分方案是num=max_num+0，
除此之外再考虑最大加数变小的情况，即max_num-1.
"""


class Solution:
    def func(self, num, max_num):
        if num < 1 or max_num < 1:
            return 0
        if num == 1 or max_num == 1:
            return 1
        if num < max_num:
            return self.func(num, num)
        if num == max_num:
            return 1 + self.func(num, max_num - 1)
        return self.func(num - max_num, max_num) + self.func(num, max_num - 1)


print(Solution().func(4, 4))
